package 背包问题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname Package0_1
 * @Description TODO
 * @Date 2022/3/24 22:21
 * @Created by xjl
 */
public class OnePackage {
    /**
     * @description 0-1背包问题的算法
     * @param: i
     * @param: c
     * @date: 2022/3/24 22:55
     * @return: int
     * @author: xjl
     */
    private int OnePackage(int[] v, int[] w, int k, int c) {
        int[][] result = new int[k + 1][c + 1];
        // 正式的1行1列的时候
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= c; j++) {
                //判断是否能装下该容量
                if (j < w[i]) {
                    result[i][j] = result[i - 1][j];
                } else {
                    result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        return result[k][c];
    }

    /**
     * @description 如果在w v的时候没有的给0的时候，自己要记得给，方便计算。
     * @param:
     * @date: 2022/3/25 15:10
     * @return: void
     * @author: xjl
     */
    @Test
    public void getMaxvalue() {
        // 表示物品的容量
        int[] w = {0, 2, 3, 4, 5};
        // 表示物品的价值
        int[] v = {0, 3, 4, 5, 6};
        int k = 4, c = 8;
        int i = OnePackage(v, w, k, c);
        System.out.println(i);
    }

    /**
     * @description 发现的最大时候有哪些在背包里面
     * @param: v
     * @param: w
     * @param: k
     * @param: c
     * @date: 2022/3/25 15:13
     * @return: void
     * @author: xjl
     */
    private List<Integer> Find(int[] w, int[] v, int k, int c) {
        int[][] dp = new int[k + 1][c + 1];
        // 正式的1行1列的时候
        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= c; j++) {
                //判断是否能装下该容量
                if (j < w[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        int i = dp.length - 1;
        int j = c;
        while (i > 0 || j > 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            } else {
                res.add(i);
                j = j - v[i];
                i--;
            }
        }
        return res;
    }

    /**
     * @description 回溯找到的那些物品被放入在背包里面
     * @param:
     * @date: 2022/3/25 15:12
     * @return: void
     * @author: xjl
     */
    @Test
    public void getindex() {
        // 表示物品的容量
        int[] w = {0, 2, 3, 4, 5};
        // 表示物品的价值
        int[] v = {0, 3, 4, 5, 6};
        int k = 4, c = 8;
        List<Integer> find = Find(w, v, k, c);
        for (int i : find) {
            System.out.println(i);
        }
    }
}